package DynamicProgramming;//给定一个三角形 triangle ，找出自顶向下的最小路径和。
//
// 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果
//正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
//输出：11
//解释：如下面简图所示：
//   2
//  3 4
// 6 5 7
//4 1 8 3
//自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
// 
//
// 示例 2： 
//
// 
//输入：triangle = [[-10]]
//输出：-10
// 
//
// 
//
// 提示： 
//
// 
// 1 <= triangle.length <= 200 
// triangle[0].length == 1 
// triangle[i].length == triangle[i - 1].length + 1 
// -10⁴ <= triangle[i][j] <= 10⁴ 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？ 
// 
// Related Topics 数组 动态规划 👍 1015 👎 0


import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class minimumTotal {
    //正确的,时间复杂度 n^2  空间复杂度n^2
    public int minimumTotal(List<List<Integer>> triangle) {
        //二维dp，dp[i][j]表示到达(i,j)位置的最小路径和，最后取最后一层的最小值即结果
        //优化空间的话，可以考虑直接在triangle上改
        int len = triangle.size();
        int[][] dp = new int[len][len];
        //对于dp[i][j]来说当j等于0时，它的状态取决于dp[i-1][0]，只能从它过来
        //对于dp[i][j] i==j时，它的状态取决于dp[i-1][j-1],只能从它过来
        //其它情况dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + 当前值
        dp[0][0] = triangle.get(0).get(0);  //初始化
        //从第一行开始
        for(int i=1;i<len;i++){
            for(int j=0;j<=i;j++){
                //状态转移三种情况
                if(j==0){
                    dp[i][j] = dp[i-1][0] + triangle.get(i).get(j);
                }else if(i==j){
                    dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
                }else{
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle.get(i).get(j);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        //遍历dp i为len-1的那一层，取最小
        for(int i=0;i<len;i++){
            res = Math.min(res,dp[len-1][i]);
        }

        return res;
    }

    /**
     * 不需要空间复杂度，直接在原数组上改
     * */
    public int minimumTotal2(List<List<Integer>> triangle) {
        //二维dp，dp[i][j]表示到达(i,j)位置的最小路径和，最后取最后一层的最小值即结果
        //优化空间的话，可以考虑直接在triangle上改
        int len = triangle.size();
        //从第一行开始
        for(int i=1;i<len;i++){
            List<Integer> curList = triangle.get(i);  //当前层的集合
            for(int j=0;j<=i;j++){
                int num = curList.get(j);  //获取当前位置的值
                //状态转移三种情况
                if(j==0){
                    curList.set(j,triangle.get(i-1).get(0) + num);
                }else if(i==j){
                    curList.set(j,triangle.get(i-1).get(j-1) + num);
                }else{
                    curList.set(j,Math.min(triangle.get(i-1).get(j),triangle.get(i-1).get(j-1)) + num);
                }
            }
        }
        Integer integer = triangle.get(len - 1).stream().min(((o1, o2) -> o1 - o2)).get();
        int res = Integer.MAX_VALUE;
        //遍历最后一层
        for(int i:triangle.get(len-1)){
            res = Math.min(res,i);
        }
        return integer;
    }



    public int minimumTotal1(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0){
            return 0;
        }
        //设dp[i] 表示第i层的最小路径和
        //那么对于i层来说，遍历当前层的每一个节点和下一层的对应节点值的和取最小，且取最小
        int level = triangle.size();
        int[] dp = new int[level+1];
        for(int i=level-1; i>=0 ;i--){
            List<Integer> curTr = triangle.get(i);
            for(int j=0;j<curTr.size();j++){
                //这里的dp[j] 使用的时候默认是上一层的，赋值之后变成当前层
                dp[j] = Math.min(dp[j],dp[j+1]) + curTr.get(j);
            }
        }
        return dp[0];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
